package com.spd.link;

/**
 * 双向链表，实现三种功能，插入、删除、查找操作。
 * @author xianchao
 *
 */
public class DoubleLinkedList {
	//设定一个哨兵节点，该节点没有实际意义，只是为了简化代码操作而设定的。
	private Node sentinelNode;
	//哨兵值，一个标示值，无实际意义。
	public static final int SENTINEVALUE = -999;
	/**
	 * 初始化操作，初始化哨兵节点
	 */
	public void init() {
		sentinelNode = new Node();
		//假定-999为无效值
		sentinelNode.setValue(SENTINEVALUE);
		//设定该哨兵的前驱和后继都为自己
		sentinelNode.setNextNode(sentinelNode);
		sentinelNode.setPreNode(sentinelNode);
	}
	
	/**
	 * 在链表的末尾追加节点，
	 * 操作过程是，找到哨兵的前驱，
	 * 1. 把它的前驱的后继改为插入的节点
	 * 2. 把插入元素的前驱改为该前驱节点。
	 * 3. 把插入元素的后继改为该节点
	 * @param node
	 */
	public void add(Node node) {
		//哨兵的前驱即为最后一个节点
		Node lastNode = sentinelNode.getPreNode();
		lastNode.setNextNode(node);
		node.setPreNode(lastNode);
		node.setNextNode(sentinelNode);
		sentinelNode.setPreNode(node);
	}

	/**
	 * 在值为value的节点之后插入节点
	 * @param itemNode
	 * @param value
	 */
	public void insert(Node itemNode, int value) {
		//1. 遍历，找到值为value的节点，然后插入
		Node node = sentinelNode.getNextNode();
		while(node.getValue() != SENTINEVALUE) {
			if(node.getValue() == value) {
				Node nextNode = node.getNextNode();
				node.setNextNode(itemNode);
				itemNode.setNextNode(nextNode);
				itemNode.setPreNode(node);
				nextNode.setPreNode(itemNode);
				break;
			}
			node = node.getNextNode();
		}
	}
	
	/**
	 * 删除链表中的某个节点
	 * @param value
	 */
	public void delete(int value) {
		Node node = sentinelNode.getNextNode();
		while(node.getValue() != -999) {
			if(node.getValue() == value) {
				Node preNode = node.getPreNode();
				Node nextNode = node.getNextNode();
				preNode.setNextNode(nextNode);
				nextNode.setPreNode(preNode);
				break;
			}
		}
	}
	
	/**
	 * 遍历输出链表
	 */
	public void printList() {
		//直接跳过第一个哨兵节点
		Node node = sentinelNode.getNextNode();
		while(node.getValue() != -999) {
			System.out.print(node.getValue() + " ");
			node = node.getNextNode();
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		doubleLinkedList.init();
		//追加
		for(int i = 1; i < 10; i++) {
			Node node = new Node();
			node.setValue(i);
			doubleLinkedList.add(node);
		}
		doubleLinkedList.printList();
		//插入一个要素
		Node insertNode = new Node();
		insertNode.setValue(20);
		doubleLinkedList.insert(insertNode, 0);
		System.out.println("插入后：");
		doubleLinkedList.printList();
		//删除
		int deleteValue = 1;
		doubleLinkedList.delete(deleteValue);
		System.out.println("删除后：");
		doubleLinkedList.printList();
	}
}

